import functools


class Solution(object):
    def isValidPalindrome(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: bool
        """
        @functools.cache
        def search(i, j, k):
            if i == j:
                return True
            else:
                if j - 1 == 1:
                    if s[i] != s[j] and k == 0:
                        return False
                else:
                    if k >= j - i:
                        return True
                    if s[i] == s[j]:
                        return search(i + 1, j - 1, k)
                    else:
                        if k == 0:
                            return False
                        else:
                            return search(i + 1, j, k - 1) or search(i, j - 1, k - 1)
        return search(0, len(s) - 1, k)


data = Solution()
s = "abcdeca"
k = 100
print(data.isValidPalindrome(s, k))
